package leetcode.daily;

import java.util.Arrays;

/**
 * @author : zx
 * @version V1.0
 */
public class med_difficult_20201215 {

    /**
     *
     * 面试题 04.08. 首个共同祖先
     * 设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
     *
     * 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
     *
     *     3
     *    / \
     *   5   1
     *  / \ / \
     * 6  2 0  8
     *   / \
     *  7   4
     * 示例 1:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出: 3
     * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
     * 示例 2:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出: 5
     * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     * 说明:
     *
     * 所有节点的值都是唯一的。
     * p、q 为不同节点且均存在于给定的二叉树中。
     *
     * Definition for a binary tree node.
     *
     */
    public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 分为在子树同时找到 找到一边 和 是根节点自身 三种情况
        // 自身直接返回
        if(root == null || root == p || root == q) return root;
        TreeNode left = null;
        TreeNode right = null;
        if(root.left != null) left = lowestCommonAncestor(root.left, p, q);
        if(root.right != null) right = lowestCommonAncestor(root.right, p, q);
        if(right != null && left != null) return root;  // 两边都找的到 一定在root
        return left==null ? right : left; // 两边至少有一边找到 ？ 这取决于p q 是否同时在一棵子树中，
        // 如果在同一子树中 则返回的是最近公共祖先 不在的话则返回递归中一方的路径
    }

    /**
     * 885. 螺旋矩阵 III
     * 在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始
     *
     * 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
     *
     * 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
     *
     * 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
     *
     * 最终，我们到过网格的所有 R * C 个空间。
     *
     * 按照访问顺序返回表示网格位置的坐标列表。
     *
     *
     *
     * 示例 1：
     *
     * 输入：R = 1, C = 4, r0 = 0, c0 = 0
     * 输出：[[0,0],[0,1],[0,2],[0,3]]
     *
     *
     *
     *
     * 示例 2：
     *
     * 输入：R = 5, C = 6, r0 = 1, c0 = 4
     * 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
     *
     *
     *
     *
     * 提示：
     *
     * 1 <= R <= 100
     * 1 <= C <= 100
     * 0 <= r0 < R
     * 0 <= c0 < C
     */
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int nums = Math.max(
                Math.max(R-r0-1, r0),
                Math.max(C-c0-1, c0)
        ); // 最大圈数 1本身为0圈
        int[][] res = new int[R*C][2];
        res[0][0] = r0;
        res[0][1] = c0;
        int n = 1; // 记录坐标数
        int c = c0, r = r0;
        for(int i = 1; i <= nums; i++){
            // 顺时针起点在正右边 然后向下移nums 然后向左移2*nums 然后向上移2*nums 然后向右移2*nums 然后向下移 nums-1
            c += 1;
            r = r;
            if(r < R && r >= 0 && c < C && c >= 0){
                res[n][0] = r;
                res[n][1] = c;
                n++;
            }
            for(int j = 1; j < 2*i; j++){
                r += 1;
                if(r < R && r >= 0 && c < C && c >= 0){
                    res[n][0] = r;
                    res[n][1] = c;
                    n++;
                }
            }
            for(int j = 1; j <= 2*i; j++){
                c -= 1;
                if(r < R && r >= 0 && c < C && c >= 0){
                    res[n][0] = r;
                    res[n][1] = c;
                    n++;
                }
            }
            for(int j = 1; j <= 2*i; j++){
                r -= 1;
                if(r < R && r >= 0 && c < C && c >= 0){
                    res[n][0] = r;
                    res[n][1] = c;
                    n++;
                }
            }
            for(int j = 1; j <= 2*i; j++){
                c += 1;
                if(r < R && r >= 0 && c < C && c >= 0){
                    res[n][0] = r;
                    res[n][1] = c;
                    n++;
                }
            }
        }
        return res;
    }

    /**
     * 436. 寻找右区间
     * 给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。
     *
     * 对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。
     *
     * 注意:
     *
     * 你可以假设区间的终点总是大于它的起始点。
     * 你可以假定这些区间都不具有相同的起始点。
     * 示例 1:
     *
     * 输入: [ [1,2] ]
     * 输出: [-1]
     *
     * 解释:集合中只有一个区间，所以输出-1。
     * 示例 2:
     *
     * 输入: [ [3,4], [2,3], [1,2] ]
     * 输出: [-1, 0, 1]
     *
     * 解释:对于[3,4]，没有满足条件的“右侧”区间。
     * 对于[2,3]，区间[3,4]具有最小的“右”起点;
     * 对于[1,2]，区间[2,3]具有最小的“右”起点。
     * 示例 3:
     *
     * 输入: [ [1,4], [2,3], [3,4] ]
     * 输出: [-1, 2, -1]
     *
     * 解释:对于区间[1,4]和[3,4]，没有满足条件的“右侧”区间。
     * 对于[2,3]，区间[3,4]有最小的“右”起点。
     * @param intervals
     * @return
     */
    public int[] findRightInterval(int[][] intervals) {
        int len = intervals.length;
        int[][] ranges = new int[len][3];
        int[] result = new int[len];
        for(int i = 0; i < len; i++){
            ranges[i] = new int[]{intervals[i][0], intervals[i][1], i};
        }
        Arrays.sort(ranges, (o1,o2)->{return o1[0]-o2[0];}); // 起点排序
        for(int i = 0; i < len; i++){
            int k = binarySearch(ranges, ranges[i][1], i+1, len-1);
            result[ranges[i][2]] = k==-1 ? -1 : ranges[k][2];
        }
        return result;
    }

    private int binarySearch(int[][] data, int target, int l, int r){
        int left = l, right = r;
        if(left > right) return -1;
        // 找最小的大于target的left
        while (left <= right){
            int mid = left + (right-left)/2;
            if(data[mid][0] < target) left = mid+1;
            else if(data[mid][0] > target) right = mid-1;
            else return mid;
        }
        if(right+1 <= r && data[right+1][0] >= target) return right+1;
        else return -1;
    }


    /**
     *
     * 1659. 最大化网格幸福感
     * 给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。
     *
     * 请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，不必 让所有人都生活在网格中。
     *
     * 每个人的 幸福感 计算如下：
     *
     * 内向的人 开始 时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会 失去  30 个幸福感。
     * 外向的人 开始 时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会 得到  20 个幸福感。
     * 邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。
     *
     * 网格幸福感 是每个人幸福感的 总和 。 返回 最大可能的网格幸福感 。
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
     * 输出：240
     * 解释：假设网格坐标 (row, column) 从 1 开始编号。
     * 将内向的人放置在单元 (1,1) ，将外向的人放置在单元 (1,3) 和 (2,3) 。
     * - 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (0 * 30)（0 位邻居）= 120
     * - 位于 (1,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
     * - 位于 (2,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
     * 网格幸福感为：120 + 60 + 60 = 240
     * 上图展示该示例对应网格中每个人的幸福感。内向的人在浅绿色单元中，而外向的人在浅紫色单元中。
     * 示例 2：
     *
     * 输入：m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
     * 输出：260
     * 解释：将内向的人放置在单元 (1,1) 和 (3,1) ，将外向的人放置在单元 (2,1) 。
     * - 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
     * - 位于 (2,1) 的外向的人的幸福感：40（初始幸福感）+ (2 * 20)（2 位邻居）= 80
     * - 位于 (3,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
     * 网格幸福感为 90 + 80 + 90 = 260
     * 示例 3：
     *
     * 输入：m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
     * 输出：240
     *
     *
     * 提示：
     *
     * 1 <= m, n <= 5
     * 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)
     *
     * 方法的思路是，一个格子一个格子自的搜索（而非一行一行的搜索）。
     *
     * 每搜索一个格子，它只可能影响它左边的和上边的格子。
     *
     * 而一个格子上边的格子，距离它为 n，这里大神有很好的图示：https://leetcode-cn.com/problems/maximize-grid-happiness/solution/you-yi-chong-zhuang-ya-jiao-zuo-hua-dong-chuang-ko/
     *
     * 所以，我们只需要记录最近的 n 个安排就好。
     *
     * 对于这个思路，状态是：dp[x][y][in][ex][laststate]。
     *
     * 表示：现在在 x, y 的位置，还有 in 个内向的人和 ex 个外向的人没有安排；同时，之前 n 个格子的安排方式是 laststate。
     *
     *
     *
     * 此时，我们只需要计算出 mod = 3^(n - 1)，那么对于一个格子，它的上面格子的安排，就是 state / mod（如果有上面的话）；左面格子的安排，就是 state % 3（如果有左面的话）。也就是 state 这个三进制数地第一个数字和最后一个数字。
     *
     * 我们就可以针对当前格子的三种选择：不安排，安排内向或者安排外向，来决定当前格子的分数，以及左边和上边格子的调整值。
     *
     * 作者：liuyubobobo
     * 链接：https://leetcode-cn.com/problems/maximize-grid-happiness/solution/dong-tai-gui-hua-shi-jian-qia-de-you-dian-er-jin-y/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    private int statemax = 1, mod = 0, R = 0, C = 0;
    private int[][][][][] dp;

    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {

        R = m;
        C = n;
        for(int i = 0; i < n; i ++) statemax *= 3;
        mod = statemax / 3;

        dp = new int[m][n][introvertsCount + 1][extrovertsCount + 1][statemax];
        return dfs(0, 0, introvertsCount, extrovertsCount, 0);
    }

    private int dfs(int x, int y, int in, int ex, int last){

        if(x == R) return 0;
        if(y == C) return dfs(x + 1, 0, in, ex, last); // 有到达边界，直接看下一行
        if(dp[x][y][in][ex][last] != 0) return dp[x][y][in][ex][last];

        // 不安排
        int res = dfs(x, y + 1, in, ex, last % mod * 3);

        // 安排内向
        if(in != 0) {
            int t1 = 120, up = last / mod, left = last % 3;
            if (x - 1 >= 0 && up != 0) {
                t1 -= 30;
                t1 += up == 1 ? -30 : 20;
            }
            if (y - 1 >= 0 && left != 0) {
                t1 -= 30;
                t1 += left == 1 ? -30 : 20;
            }
            res = Math.max(res, t1 + dfs(x, y + 1, in - 1, ex, last % mod * 3 + 1));
        }

        // 安排外向
        if(ex != 0) {
            int t2 = 40, up = last / mod, left = last % 3;;
            if (x - 1 >= 0 && up != 0) {
                t2 += 20;
                t2 += up == 1 ? -30 : 20;
            }
            if (y - 1 >= 0 && left != 0) {
                t2 += 20;
                t2 += left == 1 ? -30 : 20;
            }
            res = Math.max(res, t2 + dfs(x, y + 1, in, ex - 1, last % mod * 3 + 2));
        }
        return dp[x][y][in][ex][last] = res;
    }


    public static void main(String[] args){
        med_difficult_20201215 a = new med_difficult_20201215();
        System.out.println(Arrays.toString(a.findRightInterval(
                new int[][]{
                        new int[]{3,4},
                        new int[]{2,3},
                        new int[]{1,2},
                }
        )));
    }

}
